Pow(X,N)

Time: O(LogN)=O(1); Space: O(1); medium

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: x = 2.00000, n = 10

Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3

Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2

Output: 0.25000

Explanation:

  • 2-2 = 1/22 = 1/4 = 0.25

Constraints:

  • -100.0 < x < 100.0

  • n is a 32-bit signed integer, within the range (-2^31, 2^31-1)

[8]:

class Solution1(object):
    def myPow(self, x, n) -> float:
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        result = 1
        abs_n = abs(n)

        while abs_n:
            if abs_n & 1:
                result *= x
            abs_n >>= 1
            x *= x

        return 1.0 / result if n < 0 else result

[13]:

s = Solution1()
x = 2.00000
n = 10
assert s.myPow(x, n) == 1024.00000

x = 2.10000
n = 3
assert s.myPow(x, n) == 9.261000000000001

x = 2.00000
n = -2
assert s.myPow(x, n) == 0.25000

[10]:

class Solution2(object):
    """
    Time: O(logN); Space: O(logN)
    """
    def myPow(self, x, n) -> float:
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0 and n != -n:
            return 1.0 / self.myPow(x, -n)
        if n == 0:
            return 1
        v = self.myPow(x, n // 2)

        if n % 2 == 0:
            return v * v
        else:
            return v * v * x

[14]:

s = Solution2()
x = 2.00000
n = 10
assert s.myPow(x, n) == 1024.00000

x = 2.10000
n = 3
assert s.myPow(x, n) == 9.261000000000001

x = 2.00000
n = -2
assert s.myPow(x, n) == 0.25000